// 给你一个链表数组，每个链表都已经按升序排列。
// 请你将所有链表合并到一个升序链表中，返回合并后的链表。

// 示例 1：

// 输入：lists = [[1,4,5],[1,3,4],[2,6]]
// 输出：[1,1,2,3,4,4,5,6]
// 解释：链表数组如下：
// [
//   1->4->5,
//   1->3->4,
//   2->6
// ]
// 将它们合并到一个有序链表中得到。
// 1->1->2->3->4->4->5->6

// ListNode的定义
// function ListNode(val, next) {
//   this.val = (val===undefined ? 0 : val)
//   this.next = (next===undefined ? null : next)
// }

function mergeKLists(lists) {
  // 处理空数组情况
  if (lists.length === 0) {
    return null;
  }

  // 处理非空数组情况
  while (lists.length > 1) {
    // 合并两个链表
    const mergedList = mergeTwoLists(lists[0], lists[1]);
    // 删除已合并的链表
    lists.splice(0, 2);
    // 将合并后的链表添加到数组末尾
    lists.push(mergedList);
  }

  return lists[0];
}

function mergeTwoLists(l1, l2) {
  // 处理空链表情况
  if (l1 === null) {
    return l2;
  }
  if (l2 === null) {
    return l1;
  }

  // 递归合并: 比较 l1 和 l2 的头节点，将较小的节点作为新链表的头节点，
  // 然后递归合并剩余的节点。
  if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
}